package com.conjane.algo.linked_list;

/**
 * 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0开头。
 */
public class AddTwoNumber {

    private static ListNode<Long> add(ListNode<Long> l1,ListNode<Long> l2){
        long l1Value = 0;
        int digit = 0;
        while (l1.next != null){
            int pow = (int)Math.pow(10,digit);
            Long val = l1.next.val;
            l1Value = l1Value + pow * val;
            l1 = l1.next;
            digit++;
        }
        digit = 0;
        long l2Value = 0;
        while (l2.next != null){
            int pow = (int)Math.pow(10,digit);
            Long val = l2.next.val;
            l2Value = l2Value + pow * val;
            l2 = l2.next;
            digit++;
        }
        long sum = l1Value + l2Value;
        ListNode<Long> head = new ListNode<>();
        if (sum == 0){
            head.add(0L);
            return head;
        }
        while (sum != 0){
            long l = sum % 10;
            sum = sum / 10;
            head.add(l);
        }
        return head;
    }

    /**
     * 优化解法：
     * 1：遍历两个链表
     * 2：对应位置的节点数值相加，如果两个链表的长度不一致，则短链表高位为0
     * 3：将计算结果插入新链表尾部，大于10，则进位，最后需要将进位插入到链表尾部
     * @param l1
     * @param l2
     * @return
     */
    private static ListNode<Long> addPlus(ListNode<Long> l1,ListNode<Long> l2){
        ListNode<Long> p = l1,q = l2;
        ListNode<Long> resultNode = new ListNode<>();
        ListNode<Long> tempNode = resultNode;
        long carry = 0; //进位
        // 构造的节点又头结点，所以需要next
        while (p.next != null || q.next != null){
            long x = p.next != null ? p.next.val : 0; // 如果p不为空，则取p节点数值，否则为0
            long y = q.next != null ? q.next.val : 0; // 如果q不为空，则取q节点数值，否则为0
            long sum = x + y + carry; // 两个数值相加，并且加上进位，为数值和
            carry = sum / 10; // 取整拿到进位
            long num = sum % 10; // 取余拿到数值

            // 根据num节点，插入到结果链表中
            tempNode.next = new ListNode<>(num);
            tempNode = tempNode.next;
            p = p == null ? p : p.next;
            q = q == null ? q : q.next;
        }

        // 如果产生进位则在最后节点中加入进位节点
        if (carry > 0){
            tempNode.next = new ListNode<>(carry);
        }
        return resultNode;
    }

    public static void main(String[] args) {
        ListNode<Long> l1 = new ListNode<>();
        l1.add(2L);
        l1.add(4L);
        l1.add(3L);
        ListNode<Long> l2 = new ListNode<>();
        l2.add(5L);
        l2.add(6L);
        l2.add(4L);
        ListNode<Long> sum = addPlus(l1, l2);
        System.out.println(sum);
    }
}
